Traditional entropy encoding coding algorithms (such as Huffman coding, adaptive Huffman coding or range coding) can normally be improved by preprocessing their input using a technique designed to enhance the statistical features used by the compression algorithm to achieve coding efficiencies. One example of such a technique is the Burrows-Wheeler transform (“BWT”), where large blocks of input are rearranged in a sorted order. While BWT does improve compression efficiency, it does not replace symbol values, so it may not be as efficient on input streams with a wide variance in symbols, or streams where a large number of the symbols have high values.
Context models have been used in prediction by partial matching (PPM) coding techniques. However, adaptive entropy coders that use a prediction by partial matching context model use a lot of memory—the amount in use tends to grow exponentially with the size of contexts. Even a relatively short context of 3 characters can use tens or hundreds of megabytes of memory for context tables. Even worse, if the decompressor does not have enough memory available to construct all of the context tables, the compressed stream cannot be decompressed. Even worse than that, the decompressor may not know it cannot successfully process a compressed data stream until it runs out of memory.